Abstract:

In this talk I will introduce constructions of finite graphs which resemble some given infinite graph both in terms of their local neighborhoods, and also their spectrum. These graphs can be thought of as expander graphs with local constraints in a constant-sized neighborhood, and generalize the notion of d-regular Ramanujan graphs.

First, I will show how a "recipe" in the form of some matrix-coefficient non-commutative polynomial can be used to specify many infinite graphs, including those arising from various graph products, and also generate finite graphs which are covered by the infinite graph. A recent landmark result of Bordenave and Collins implies that for all such graphs, with high probability the finite graphs generated with this recipe also have their nontrivial spectrum close to that of the infinite graph.

Next, I will talk about a derandomized form of this result: we provide a deterministic polynomial-time algorithm which, for any X which can arise from a matrix-coefficient polynomial, produces arbitrarily large graphs G that are covered by X and have (nontrivial) spectrum at Hausdorff distance at most eps from that of X.

Joint work with Ryan O'Donnell.